import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution01 {
    // 创建两个哈希表
    Set<String> hashSetBank = new HashSet<>();
    Set<String> hashSet = new HashSet<>();// 用来标记

    public int minMutation(String startGene, String endGene, String[] bank) {
        // 将bank数组转换为哈希表
        for (String s : bank) {
            hashSetBank.add(s);
        }
        // 创建一个字符数组
        char[] change = {'A', 'C', 'G', 'T'};
        // 处理边界情况
        if (startGene.equals(endGene)) {
            return 0;
        }
        if (!hashSetBank.contains(endGene)) {
            return -1;
        }
        // 创建一个队列 里面存储字符串
        Queue<String> q = new LinkedList<>();
        // 将startGene 入队
        q.offer(startGene);
        // 对队头元素进行标记
        hashSet.add(startGene);

        // 记录结果
        int ret = 0;

        while (!q.isEmpty()) {
            ret++;
            // 循环 队列里面元素的个数 次
            int sz = q.size();
            while (sz-- != 0) {
                // 弹出队头元素
                String t = q.poll();
                // 把队头元素里面的字符进行改变 对该字符串进行从头到尾进行遍历
                for (int i = 0; i < 8; i++) {
                    // 对字符串进行强转
                    char[] tmp = t.toCharArray();
                    for (int j = 0; j < 4; j++) {
                        tmp[i] = change[j];
                        // 将该数组转换为字符串
                        String next = new String(tmp);
                        // 进行判断是否合法
                        if (hashSetBank.contains(next) && !hashSet.contains(next)) {
                            if (next.equals(endGene)) {
                                return ret;
                            }
                            q.add(next);
                            hashSet.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}